The present invention relates to the technical field of methods, systems and devices designed to prove the authenticity of an entity and/or the integrity and/or authenticity of a message.
The patent EP 0 311 470 B1, whose inventors are Louis Guillou and Jean-Jacques Quisquater, describes such a method. Hereinafter, reference shall be made to their work by the terms “GQ patent” or “GQ method”. Hereinafter, the expression “GQ2”, or “GQ2 invention” or “GQ2 technology” shall be used to describe the new developments of the GQ technology that are the object of pending applications filed on the same day as the present application by France Telecom, TDF and the firm Mathrizk, and having Louis Guillou and Jean-Jacques Quisquater as their inventors. The characteristic features of these pending applications are recalled whenever necessary in the following description.
According to the GQ method, an entity known as a “trusted authority” assigns an identity to each entity called a “witness” and computes its RSA signature. In a customizing process, the trusted authority gives the witness an identity and signature. Thereafter, the witness declares the following: “Here is my identity; I knew the RSA signature thereof”. The witness, without revealing the fact, proves that he knows the RSA signature of his identity. Through the RSA public identification key distributed by the trusted authority, an entity known as a “controller” ascertains, without obtaining knowledge thereof, that the RSA signature corresponds to the declared identity. The mechanism using the GQ method takes place “without transfer of knowledge”. According to the GQ method, the witness does not know the RSA private key with which the trusted authority signs a large number of identities.
The GQ technology described here above makes use of RSA technology. However, while the RSA technology truly depends on the factorization of the modulus n, this dependence is not an equivalence, indeed far from it, as can be seen in the so-called multiplicative attacks against various standards of digital signatures implementing the RSA technology.
The goal of the GQ2 technology is twofold: firstly to improve the performance characteristics of RSA technology and secondly to avert the problems inherent in RSA technology. Knowledge of the GQ2 private key is equivalent to knowledge of the factorization of the modulus n. Any attack on the triplets GQ2 leads to the factorization of the modulus n: this time there is equivalence. With the GQ2 technology, the work load is reduced for the signing or self-authenticating entity and for the controlling entity. Through a better use of the problem of factorizing in terms of both security and performance, the GQ2 technology averts the drawbacks of RSA technology.
The GQ method implements modulo computations of numbers comprising 512 bits or more. These computations relate to numbers having substantially the same size raised to powers of the order of 216+1. Now, existing microelectronic infrastructures, especially in the field of bank cards, make use of monolithic self-programmable microprocessors without arithmetical coprocessors. The work load related to multiple arithmetical applications involved in methods such as the GQ method leads to computation times which, in certain cases, prove to be disadvantageous for consumers using bank cards to pay for their purchases. It may be recalled here that, in seeking to increase the security of payment cards, the banking authorities have raised a problem that is particularly difficult to resolve. Indeed, two apparently contradictory questions have to be resolved: on the one hand, increasing safety by using increasingly lengthy and distinct keys for each card while, on the other hand, preventing the work load from leading to excessive computation times for the user. This problem becomes especially acute inasmuch as it is also necessary to take account of the existing infrastructure and the existing microprocessor components.